#pragma once
#include<iostream>
#include<vector>
#include<string>

using namespace std;
namespace Hash_Bucket
{
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _p;
		HashData<K, V>* _next;

		HashData(const pair<K, V>& p)
			:_next(nullptr),
			_p(p)
		{}
	};

	template<class K>
	class HashFunc
	{
	public:
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	class HashFunc<string>
	{
	public:
		size_t operator()(const string& s)
		{
			int ret = 0;
			for (auto e : s)
			{
				// BKDR
				ret *= 31;
				ret += e;
			}
			return ret;
		}
	};

	template<class K, class V ,class Hash = HashFunc<K>>
	class HashBucket
	{
		typedef HashData<K, V> Node;
	public:
		HashBucket(size_t n = 10)
			:_num(0)
		{
			_v.resize(n);
		}

		bool insert(const pair<K, V>& p)
		{
			if (find(p.first))
			{
				return false;
			}

			Hash hs;

			if (_num * 10 % _v.size() >= 1)
			{
				vector<Node*> newV;
				newV.resize(_v.size() * 2);

				for (const auto& e : _v)
				{
					Node* cur = e;
					while (cur)
					{
						Node* next = cur->_next;
						size_t Hashi = hs(cur->_p.first) % newV.size();
						
						cur->_next = newV[Hashi];
						newV[Hashi] = cur;
						cur = next;
					}
				}

				_v.swap(newV);
			}

			size_t Hashi = hs(p.first) % _v.size();
			Node* newnode = new Node(p);

			newnode->_next = _v[Hashi];
			_v[Hashi] = newnode;

			++_num;

			return true;
		}

		Node* find(const K& key)
		{
			Hash hs;
			size_t Hashi = hs(key) % _v.size();
			Node* cur = _v[Hashi];
			while (cur)
			{
				if (cur->_p.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		bool erase(const K& key)
		{
			Hash hs;
			size_t Hashi = hs(key) % _v.size();
			Node* cur = _v[Hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_p.first == key)
				{
					prev->_next = cur->_next;
					--_num;
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _v;
		size_t _num;
	};
}